#!/usr/bin/env python3
from typing import *


class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0] * len(cost)
        dp[0] = cost[0]
        dp[1] = cost[1]
        for i in range(2, len(cost)):
            dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
        # return min(dp[len(cost) - 1], dp[len(cost)-2]);
        return min(dp[-1], dp[-2])

# 换一种写法
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = []
        dp.append(cost[0])
        dp.append(cost[1])
        for i in range(2, len(cost)):
            dp.append(min(dp[i-1], dp[i-2]) + cost[i])
        # return min(dp[len(cost) - 1], dp[len(cost)-2]);
        return min(dp[-1], dp[-2])

# 直接修改const数组----减少内存占用同时不用初始化
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        for i in range(2, len(cost)):
            cost[i] = min(cost[i-1], cost[i-2]) + cost[i]
        # return min(cost[len(cost) - 1], cost[len(cost)-2]);
        return min(cost[-1], cost[-2])


def main():
    solu = Solution()
    cost = [10, 15, 20]
    print(solu.minCostClimbingStairs(cost))


if __name__ == '__main__':
    main()